ABC 116 D - Various Sushi
ABC 116 D - Various Sushi
貪欲
BinaryHeapを用いた解答
code: abc116_d.js
class Main {
solve() {
const nums = input.nextIntArr();
const k = nums1;
const table = input.nextIntRange(nums0);
const score = [];
table.sort((a,b) => a1 - b1).reverse();
const s = _.first(table, k);
const kinds = {};
s.forEach(e => kinds[e0] = (kinds[e0] ? kinds[e0] + 1: 1));
let kind = Object.keys(kinds).length;
scorekind = _.sum(s.map(s => s1));
const heap = new BinaryHeap();
s.forEach(e => {
if (kinds[e0] > 1) {
heap.push(-e1, e);
}
});
let cur = k;
while (heap.length > 0 && cur < table.length) {
const target = heap.pop();
if (kinds[target0] >= 2) {
--kinds[target0];
do {
let next = tablecur;
++cur;
if (kinds[next0] === undefined) {
kinds[next0] = 1;
++kind;
scorekind = scorekind - 1 + next1 - target1;
break;
}
} while(cur < table.length);
}
}
const scores = score.map((e,i) => e ? (e + i * i) : 0);
console.log(_.max(scores));
}
}
値をいれた後でソートを行うことでheapをarrに置き換え可能
配列を用いた解答
code: abc116_d2.js
class Main {
solve() {
const nums = input.nextIntArr();
const k = nums1;
const table = input.nextIntRange(nums0);
const score = [];
table.sort((a,b) => -(a1 - b1));
const s = _.first(table, k);
const kinds = {};
s.forEach(e => kinds[e0] = (kinds[e0] ? kinds[e0] + 1: 1));
let kind = Object.keys(kinds).length;
scorekind = _.sum(s.map(s => s1));
const arr = [];
s.forEach(e => {
if (kinds[e0] > 1) {
arr.push(e);
}
});
arr.sort((a,b) => -(a1 - b1));
let cur = k;
while (arr.length > 0 && cur < table.length) {
const target = arr.pop();
if (kinds[target0] >= 2) {
--kinds[target0];
do {
let next = tablecur;
++cur;
if (kinds[next0] === undefined) {
kinds[next0] = 1;
++kind;
scorekind = scorekind - 1 + next1 - target1;
break;
}
} while(cur < table.length);
}
}
const scores = score.map((e,i) => e ? (e + i * i) : 0);
console.log(_.max(scores));
}
}